package _11_整理题目._4_动态规划._接雨水;

import org.junit.Test;

import java.util.PriorityQueue;

/**
 * https://leetcode-cn.com/problems/trapping-rain-water-ii/
 * 给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，
 * 请计算图中形状最多能接多少体积的雨水
 *
 * https://www.bilibili.com/video/BV1yh41187vo?spm_id_from=333.999.0.0
 */
public class _02_二维数组接雨水 {

    public int trapRainWater(int[][] matrix) {
        if (matrix == null || matrix.length < 2 || matrix[0].length < 2) return 0;

        int m = matrix.length;
        int n = matrix[0].length;
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[2]-o2[2]);
        boolean[][] visited = new boolean[m][n];
        // 将最外圈放入 queue，标记为 true
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i==0 || i==m-1 || j==0 || j==n-1) {
                    queue.add(new int[]{i, j, matrix[i][j]});
                    visited[i][j] = true;
                }
            }
        }
        int ans = 0;
        // 循环从 queue 中取元素，遍历其左上右下，如果找到比它小的内部节点，就灌水等高
        while (!queue.isEmpty()) {
            // 取出当前最小元素，i, j, x
            int[] cur = queue.poll();
            // 确定 四个方向 左 上 右 下
            int[] dir = {-1, 0, 1, 0, -1};
            // 遍历四个方向
            for (int i = 0; i < 4; i++) {
                // 取旁边节点坐标
                int nx = cur[0] + dir[i];
                int ny = cur[1] + dir[i+1];
                // 判断是否是内部节点，边界未出界，且未访问
                if (nx >= 0 && nx < m && ny >=0 && ny < n && !visited[nx][ny]) {
                    int dif = cur[2] - matrix[nx][ny];// 周围最小的墙 > 内部节点，灌水
                    if (dif > 0) {
                        ans += dif;// 收集雨水
                    }
                    // 更新新的墙，高度为 Math.max(cur[2], matrix[nx][ny])
                    queue.offer(new int[]{nx, ny, Math.max(cur[2], matrix[nx][ny])});
                    visited[nx][ny] = true;
                }
            }
        }
        return ans;
    }

    @Test
    public void main() {
        int[][] matrix = {  {1, 4, 3, 1, 3, 2},
                            {3, 2, 1, 3, 2, 4},
                            {2, 3, 3, 2, 3, 1}};
        System.out.println(trapRainWater(matrix));
    }
}
